package nsga.population;

import java.util.ArrayList;
import java.util.List;

import abstractGA.chrom.Chrom;

public class PopuHelper {
	
	/**
	 * 非支配排序
	 * @param chroms：染色体集
	 * @return：按非支配等级排序后的染色体下标数组的数组，例如：
	 * 等级0：[2,3]（pareto最优染色体下标）
	 * 等级1：[0,1]
	 */
	public ArrayList<ArrayList<Integer>> nondominatedSort(List<Chrom> chroms) {
		ArrayList<ArrayList<Integer>> idxss = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> rnk0Idxs = new ArrayList<Integer>();// 等级0（最好）的染色体下标
		ArrayList<DominateInfo> dominateInfos = new ArrayList<DominateInfo>();
		int size = chroms.size();
		for (int i = 0; i < size; i++) {
			Chrom chrom1 = chroms.get(i);
			DominateInfo dominateInfo = new DominateInfo();
			dominateInfo.idx = i;
			float resTime1 = (Float) chrom1.getObjVals().get(0);		
			float reltVal1 = (Float) chrom1.getObjVals().get(1);
			float costVal1 = (Float) chrom1.getObjVals().get(2);	
			for (int j = 0; j < size; j++) {
				Chrom chrom2 = chroms.get(j);
				if (chrom1 != chrom2) {
					float resTime2 = (Float) chrom2.getObjVals().get(0);
					float reltVal2 = (Float) chrom2.getObjVals().get(1);
					float costVal2 = (Float) chrom2.getObjVals().get(2);
					
					if ((Float.compare(resTime2, resTime1) <= 0 &&  (Float.compare(costVal2, costVal1) < 0)&&(Float.compare(reltVal2, reltVal1) >= 0))// chrom2比chrom1优
							|| (Float.compare(resTime2, resTime1) <= 0 && (Float.compare(costVal2, costVal1) <= 0)&&(Float.compare(reltVal2, reltVal1) > 0))
							|| (Float.compare(resTime2, resTime1) < 0 && (Float.compare(costVal2, costVal1) <= 0)&&(Float.compare(reltVal2, reltVal1) >= 0))) {
						dominateInfo.superiorNum += 1;
					}

					if ((Float.compare(resTime1, resTime2) <= 0 && (Float.compare(costVal1, costVal2) < 0)&&(Float.compare(reltVal1, reltVal2) >= 0))// chrom2比chrom1劣
							|| (Float.compare(resTime1, resTime2) <= 0 && (Float.compare(costVal1, costVal2) <= 0)&&(Float.compare(reltVal1, reltVal2) > 0))
							|| (Float.compare(resTime1, resTime2) < 0 && (Float.compare(costVal1, costVal2) <= 0)&&(Float.compare(reltVal1, reltVal2) >= 0))) {
						dominateInfo.inferiorIdxs.add(new Integer(j));
					}

				}
			}
			if (dominateInfo.superiorNum == 0) {
				rnk0Idxs.add(i);
			}
			dominateInfos.add(dominateInfo);
		}
		if (rnk0Idxs.size() > 0) {
			idxss.add(rnk0Idxs);
		}

		ArrayList<Integer> curRnkIdxs = rnk0Idxs;
		while (curRnkIdxs.size() > 0) {
			ArrayList<Integer> nxtRnkIdxs = new ArrayList<Integer>();
			for (Integer idx : curRnkIdxs) {
				DominateInfo curInfo = dominateInfos.get(idx);
				for (Integer inferiorIdx : curInfo.inferiorIdxs) {
					DominateInfo inferiorInfo = dominateInfos.get(inferiorIdx);
					inferiorInfo.superiorNum -= 1;
					if (inferiorInfo.superiorNum == 0) {
						nxtRnkIdxs.add(inferiorInfo.idx);
					}
				}
			}
			if (nxtRnkIdxs.size() > 0) {
				idxss.add(nxtRnkIdxs);
			}
			curRnkIdxs = nxtRnkIdxs;
		}
		return idxss;
	}

	/**
	 * 支配信息
	 * @author nyc
	 *
	 */
	protected class DominateInfo {
		int idx = -1;// 本个体在种群中的下标
		int superiorNum = 0;// 比本个体优的个体数目
		List<Integer> inferiorIdxs = new ArrayList<Integer>();// 比本个体差的个体的下标

	}

	/**
	 * 获取染色体的非支配等级
	 * @param chromIdx：染色体在种群中的下标位置
	 * @param idxss：按非支配等级排序后的染色体下标数组的数组
	 * @return：chromIdx下标染色体对应的等级
	 */
	public int getRank(int chromIdx, ArrayList<ArrayList<Integer>> idxss) {
		int rank = -1;
		int rankNum = idxss.size();

		for (int i = 0; i < rankNum; i++) {

			int chromNum = idxss.get(i).size();
			int tempChromIdx = -1;
			boolean found = false;
			for (int j = 0; j < chromNum; j++) {
				tempChromIdx = idxss.get(i).get(j);
				if (tempChromIdx == chromIdx) {
					found = true;
					break;
				}
			}
			if (found) {
				rank = i;
				break;
			}
		}

		return rank;
	}

	/**
	 * 计算pareto前沿上各个染色体对应的拥塞距离
	 * @param chroms:染色体集合（可能是种群也可能是两个种群的合集）
	 * @param frontIdxs：前沿上染色体在染色体集chroms中的下标
	 * @return：前沿上每个染色体对应的拥塞距离
	 */
	public List<Float> getCrowdDistances(List<Chrom> chroms,
			ArrayList<Integer> frontIdxs) {
		List<Float> crowdDistances = new ArrayList<Float>();
		int size = frontIdxs.size();

		if (size == 1) {
			crowdDistances.add(new Float(Float.MAX_VALUE / 1000f));
		}
		if (size == 2) {
			crowdDistances.add(new Float(Float.MAX_VALUE / 1000f));
			crowdDistances.add(new Float(Float.MAX_VALUE / 1000f));
		}

		if (size > 2) {
			for (int i = 0; i < size; i++) {
				crowdDistances.add(new Float(0f));
			}
			for (int k = 1; k <= 3; k++) {
				List<Integer> sortByFstObj = sortByObjVal(chroms, frontIdxs, k);				
				
				int idxOfMinVal = sortByFstObj.get(0);
				int idxOfMaxVal = sortByFstObj.get(size - 1);
				Object minVal = chroms.get(idxOfMinVal).getObjVals().get(k - 1);
				Object maxVal = chroms.get(idxOfMaxVal).getObjVals().get(k - 1);

				int idxInfrontIdxs = frontIdxs.indexOf(idxOfMinVal);			
				float curVal = crowdDistances.get(idxInfrontIdxs).floatValue();
				crowdDistances.set(idxInfrontIdxs, curVal + Float.MAX_VALUE
						/ 1000f);
				idxInfrontIdxs = frontIdxs.indexOf(idxOfMaxVal);
				curVal = crowdDistances.get(idxInfrontIdxs).floatValue();
				crowdDistances.set(idxInfrontIdxs, curVal + Float.MAX_VALUE
						/ 1000f);

				int idx1, idx2 = -1;

				for (int j = 1; j < size - 1; j++) {
					idx1 = frontIdxs.indexOf(sortByFstObj.get(j - 1));
					idx2 = frontIdxs.indexOf(sortByFstObj.get(j + 1));
					idxInfrontIdxs = frontIdxs.indexOf(sortByFstObj.get(j));
					float curCrowDist = crowdDistances.get(idxInfrontIdxs);
									
					float maxFloatVal = ((Float) maxVal).floatValue();
					float minFloatVal = ((Float) minVal).floatValue();
					float obj1Val = (Float) chroms.get(idx1).getObjVals().get(k - 1);
					float obj2Val = (Float) chroms.get(idx2).getObjVals().get(k - 1);

					if (Float.compare(maxFloatVal, minFloatVal) == 0) {
						crowdDistances.set(idxInfrontIdxs, 0f);
					} else {
						crowdDistances.set(idxInfrontIdxs,
								curCrowDist + (obj2Val - obj1Val) / (maxFloatVal - minFloatVal));
					}
					
				}
			}
		}

		return crowdDistances;
	}

	/**
	 * 按指定目标对前沿上的染色体进行排序
	 * @param chroms：染色体
	 * @param frontIdxs：前沿上染色体在染色体集chroms中的下标
	 * @param whichObj：按哪一个目标进行排序 
	 * @return
	 */
	public List<Integer> sortByObjVal(List<Chrom> chroms, ArrayList<Integer> frontIdxs, int whichObj) {
		List<Integer> sortResults = new ArrayList<Integer>();
		for (Integer fronIdx : frontIdxs) {
			sortResults.add(fronIdx);
		}

		int size = sortResults.size();
		for (int i = 0; i < size; i++) {
			int m = sortResults.get(i);
			Chrom chrom1 = chroms.get(m);
			Object objVal1 = chrom1.getObjVals().get(whichObj - 1);
			int idxOfMinVal = i;
			for (int j = i + 1; j < size; j++) {
				int n = sortResults.get(j);
				Chrom chrom2 = chroms.get(n);
				Object objVal2 = chrom2.getObjVals().get(whichObj - 1);
				float obj1FloatVal = ((Float) objVal1).floatValue();
				float obj2FloatVal = ((Float) objVal2).floatValue();
				if (Float.compare(obj1FloatVal, obj2FloatVal) > 0) {
					idxOfMinVal = j;
					objVal1 = objVal2;
				}
			}
			int temp = sortResults.get(i);
			sortResults.set(i, sortResults.get(idxOfMinVal));
			sortResults.set(idxOfMinVal, temp);

		}
		return sortResults;
	}
	
	/**
	 * 按拥塞距离对前沿上各个体进行排序
	 * @param dists：拥塞距离
	 * @param frontIdxs：前沿上各染色体的下标
	 * @return：按拥塞距离从大到小的顺序排好序后的前沿上染色体的下标数组
	 */
	public ArrayList<Integer> publeSort(List<Float> dists,
			ArrayList<Integer> frontIdxs) {
		ArrayList<Integer> sortedIdxs = new ArrayList<Integer>();
		for (Integer frontIdx : frontIdxs) {
			sortedIdxs.add(frontIdx);
		}

		int size = dists.size();
		for (int i = 0; i < size; i++) {
			float dist1 = dists.get(i).floatValue();
			int idxOfMaxVal = i;
			for (int j = i + 1; j < size; j++) {
				float dist2 = dists.get(j).floatValue();
				if (Float.compare(dist1, dist2) < 0) {
					dist1 = dist2;
					idxOfMaxVal = j;
				}
			}
			if (idxOfMaxVal != i) {
				float temp = dists.get(i);
				dists.set(i, dists.get(idxOfMaxVal));
				dists.set(idxOfMaxVal, temp);
				int tempInt = sortedIdxs.get(i);
				sortedIdxs.set(i, sortedIdxs.get(idxOfMaxVal));
				sortedIdxs.set(idxOfMaxVal, tempInt);
			}

		}

		return sortedIdxs;
	}

}
